#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn1 = 105;
const int maxn2 = 1005;
int n, V;
int w[maxn1];
int v[maxn1];
int dp[maxn1][maxn2]; // 表示 前 i 个物品中, 背包大小是 j 的最大价值

void solve(){
	cin >> n >> V;
	
	for (int i=1;i<=n;i++) {
		cin >> w[i] >> v[i];
	}
	
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=V;j++) {
			dp[i][j] = dp[i-1][j]; // 不取
			if (j >= w[i]) {
				// 取
				dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
			}
		}
	}
	cout << dp[n][V] << '\n';
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
